package com.hqq.exercise.cal;

/**
 * AccurateFactorial 计算精确的阶乘
 * 题目描述:输入不超过1000的正整数n，输入n!=1*2*3..*n的精确结果
 * 思路:
 * 首先初步计算1000!大概是4*10^2567 所以我们大概可以用长为3000的数组保存计算的值
 * 逆序保存 f[0]是个位 f[1]是十位 f[2]是百位..【防止出现进位溢出】
 * Created by heqianqian on 2017/8/8.
 */
public class AccurateFactorial {

    private static final int ARRAY_SIZE = 3000;

    private static int[] array;

    /**
     * 计算数的精确阶乘
     */
    public static int[] accurateFactorial(int num) {
        //每次调用重新初始化 否则数据会重复 QAQ
        array = new int[ARRAY_SIZE];
        array[0] = 1;
        for (int i = 2; i <= num; i++) {//因为1乘任何数都为本身 因此阶乘直接从2开始
            int carry = 0;//进位
            for (int j = 0; j < ARRAY_SIZE; j++) {
                int temp = array[j] * i + carry;
                array[j] = temp % 10;//个位
                carry = temp / 10;
            }
        }
        return array;
    }
}
